<!DOCTYPE html>
<html lang="en">







<head>
 <script>(function(i,s,o,g,r,a,m){i["DaoVoiceObject"]=r;i[r]=i[r]||function(){(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;a.charset="utf-8";m.parentNode.insertBefore(a,m)})(window,document,"script",('https:' == document.location.protocol ? 'https:' : 'http:') + "//widget.daovoice.io/widget/0eeeae6f.js","daovoice")
 daovoice('init', {
  app_id: "246e9537"
});
daovoice('update');
 </script>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/img/apple-touch-icon.png">
  <link rel="icon" type="image/png" href="/img/favicon.png">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="description" content="">

  <meta name="author" content="xixilili">
  <meta name="keywords" content="">
  
  <title>树形数据结构总结 ~ xixilili.blog</title>
  <link rel="stylesheet" href="https://cdn.staticfile.org/font-awesome/5.10.2/css/all.min.css"  >
<link rel="stylesheet" href="https://cdn.staticfile.org/twitter-bootstrap/4.3.1/css/bootstrap.min.css"  >
<link rel="stylesheet" href="https://cdn.staticfile.org/mdbootstrap/4.8.9/css/mdb.min.css"  >
<link rel="stylesheet" href="https://cdn.staticfile.org/github-markdown-css/3.0.1/github-markdown.min.css"  >

<link rel="stylesheet" href="//at.alicdn.com/t/font_1067060_qzomjdt8bmp.css">



  <link rel="stylesheet" href="/lib/prettify/tomorrow-night.min.css"  >

<link rel="stylesheet" href="/css/main.css"  >


  <link rel="stylesheet" href="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.css"  >


<meta name="generator" content="Hexo 4.2.0"></head>



<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/">&nbsp;<strong>xixilili.blog</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
          <li class="nav-item">
            <a class="nav-link" href="/">Home</a>
          </li>
        
          
          
          
          
          <li class="nav-item">
            <a class="nav-link" href="/archives/">Archives</a>
          </li>
        
          
          
          
          
          <li class="nav-item">
            <a class="nav-link" href="/categories/">Categories</a>
          </li>
        
          
          
          
          
          <li class="nav-item">
            <a class="nav-link" href="/tags/">Tags</a>
          </li>
        
          
          
          
          
          <li class="nav-item">
            <a class="nav-link" href="/about/">About</a>
          </li>
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="view intro-2" id="background"
         style="background: url('https://capsule-1254369940.cos.ap-chengdu.myqcloud.com/xilixiliBg.jpg')no-repeat center center;
           background-size: cover;
           background-attachment: fixed;">
      <div class="full-bg-img">
        <div class="mask rgba-black-light flex-center">
          <div class="container text-center white-text fadeInUp">
            <span class="h2" id="subtitle">
              
            </span>

            
              <br>
              
                <p class="mt-3">
                  <i class="fas fa-calendar-alt" aria-hidden="true"></i>&nbsp;
                  Wednesday, March 11th 2020, 8:40 pm
                </p>
              

              <p>
                
                  
                  &nbsp;<i class="far fa-chart-bar"></i>
                  <span class="post-count">
                    3.4k 字
                  </span>&nbsp;
                

                
                  
                  &nbsp;<i class="far fa-clock"></i>
                  <span class="post-count">
                      17 分钟
                  </span>&nbsp;
                

                
                  <!-- 不蒜子统计文章PV -->
                  
                  &nbsp;<i class="far fa-eye" aria-hidden="true"></i>&nbsp;
                  <span id="busuanzi_container_page_pv">
                    <span id="busuanzi_value_page_pv"></span> 次
                  </span>&nbsp;
                
              </p>
            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      




<div class="container-fluid">
  <div class="row">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-md">
      <div class="py-5 z-depth-3" id="board">
        <div class="post-content mx-auto" id="post">
          <div class="markdown-body">
            <h1 id="前序-中序-后序知二推一"><a href="#前序-中序-后序知二推一" class="headerlink" title="前序,中序,后序知二推一"></a>前序,中序,后序知二推一</h1><h2 id="求先序序列"><a href="#求先序序列" class="headerlink" title="求先序序列"></a>求先序序列</h2><p><strong>题目描述</strong><br>给出一棵二叉树的中序与后序排列,求出它的先序排列，(约定树结点用不同的大写字母表示,长度≤8)。</p>
<p><strong>输入格式</strong><br>2行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。</p>
<p><strong>输出格式</strong><br>1行，表示一棵二叉树的先序。</p>
<p><strong>输入</strong></p>
<blockquote>
<p>BADC<br>BDCA</p>
</blockquote>
<p><strong>输出</strong></p>
<blockquote>
<p>ABCD</p>
</blockquote>
<pre><code class="clike">#include&lt;iostream&gt;
#include&lt;string&gt;
using namespace std;

string in;
string post;

struct TreeNode{
    char data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char data):data(data),left(NULL),right(NULL){}
};

TreeNode* Tree[10000];

TreeNode* CreatTree(int s1,int t1,int s2,int t2){
    char c=post[t1];//后序的最后一个
    if(s1==t1){//叶子结点
        Tree[c-&#39;A&#39;]=new TreeNode(c);
        return Tree[c-&#39;A&#39;];
    }
    Tree[c-&#39;A&#39;]=new TreeNode(c);
    int pos=in.find(c);//在中序中找到对应的顶点以及左右长度
    int llen=pos-s2;
    int rlen=t2-pos;
    //别忘了判左右长度
    if(llen) Tree[c-&#39;A&#39;]-&gt;left=CreatTree(s1,s1+llen-1,s2,s2+llen-1);
    if(rlen) Tree[c-&#39;A&#39;]-&gt;right=CreatTree(s1+llen,t1-1,s2+llen+1,t2);
    return Tree[c-&#39;A&#39;];
}

void PreOrder(TreeNode* root){
    if(root==NULL) return ;
    cout&lt;&lt;root-&gt;data;
    PreOrder(root-&gt;left);
    PreOrder(root-&gt;right);
}

int main(){
    cin&gt;&gt;in&gt;&gt;post;
    TreeNode* root=CreatTree(0,post.size()-1,0,in.size()-1);
    PreOrder(root);
}
</code></pre>
<h2 id="求可能中序序列"><a href="#求可能中序序列" class="headerlink" title="求可能中序序列"></a>求可能中序序列</h2><p><strong>题目描述</strong><br>已知前序和后序遍历的结果求出一种可能得中序遍历的结果,二叉树的结点名以大写字母(A,B,C…)表示，最多26个结点<br><strong>输入格式</strong><br>第一行为前序遍历结果<br>第二行为后序遍历结果<br><strong>输出格式</strong><br>一个字符串，表示一个可能的中序遍历<br><strong>输入</strong></p>
<blockquote>
<p>ABDCE<br>DBECA</p>
</blockquote>
<p><strong>输出</strong></p>
<blockquote>
<p>DBAEC</p>
</blockquote>
<pre><code class="clike">#include&lt;iostream&gt;
#include&lt;string&gt;

using namespace std;

string pre,post;

struct TreeNode{
    char data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char data):data(data),left(NULL),right(NULL){}
};

TreeNode* PrePostCreat(string pre,string post){
    TreeNode* root=new TreeNode(pre[0]);
    if(pre.size()==0) return NULL;//返回
    int pos=post.find(pre[1]);//先序顶点在后序的位置
//    cout&lt;&lt;pre.substr(1,pos+1)&lt;&lt;&quot;   &quot;&lt;&lt;post.substr(0,pos+1)&lt;&lt;endl;
//    cout&lt;&lt;pre.substr(pos+2)&lt;&lt;&quot;   &quot;&lt;&lt;post.substr(pos+1,post.size()-pos-2)&lt;&lt;endl;
    root-&gt;left=PrePostCreat(pre.substr(1,pos+1),post.substr(0,pos+1));
    root-&gt;right=PrePostCreat(pre.substr(pos+2),post.substr(pos+1,post.size()-pos-2));
    return root;
}

void InOrder(TreeNode* T){
    if(T==NULL) return ;
    InOrder(T-&gt;left);
    cout&lt;&lt;T-&gt;data;
    InOrder(T-&gt;right);
}

int main(){
    cin&gt;&gt;pre&gt;&gt;post;
    TreeNode* root=PrePostCreat(pre,post);
    InOrder(root);
}
</code></pre>
<h1 id="二叉排序树"><a href="#二叉排序树" class="headerlink" title="二叉排序树"></a>二叉排序树</h1><h2 id="构造二叉排序树"><a href="#构造二叉排序树" class="headerlink" title="构造二叉排序树"></a>构造二叉排序树</h2><p><strong>题目描述</strong><br>已知二叉排序树用二叉链表存储，结点的关键字为 1正整数。从键盘输入结点的关键字（以 0表示结束）建立一棵二叉排序树，并输出其后序遍历序列</p>
<pre><code class="clike">#include&lt;iostream&gt;
#include&lt;vector&gt;
using namespace std;
vector&lt;int&gt; v;
struct TreeNode{
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int data):data(data),left(NULL),right(NULL){}
};
//x插入到以root为根结点的排序树中，从根结点不断的向下比
TreeNode* Insert(TreeNode* root,int n){
    if(root==NULL) root=new TreeNode(n);
    else if(n&lt;root-&gt;data) root-&gt;left=Insert(root-&gt;left,n);
    else if(n&gt;root-&gt;data) root-&gt;right=Insert(root-&gt;right,n);
    return root;
}
void PostOrder(TreeNode* root){
    if(root==NULL) return  ;
    PostOrder(root-&gt;left);
    PostOrder(root-&gt;right);
    cout&lt;&lt;root-&gt;data&lt;&lt;&quot; &quot;;
}
int main(){
    int n;
    TreeNode* root=NULL;
    while(cin&gt;&gt;n){
        if(n==0) break;
        else root=Insert(root,n);
    }
    PostOrder(root);
}
</code></pre>
<h2 id="二叉搜索树"><a href="#二叉搜索树" class="headerlink" title="二叉搜索树"></a>二叉搜索树</h2><p><strong>题目描述</strong><br>判断两序列是否为同一二叉搜索树序列</p>
<p><strong>输入描述:</strong><br>开始一个数n，(1&lt;=n&lt;=20) 表示有n个需要判断，n= 0 的时候输入结束。<br>接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。<br>接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。<br><strong>输出描述:</strong><br>如果序列相同则输出YES，否则输出NO</p>
<p><strong>输入</strong></p>
<blockquote>
<p>2<br>567432<br>543267<br>576342`<br>0</p>
</blockquote>
<p>输出</p>
<blockquote>
<p>YES<br>NO</p>
</blockquote>
<pre><code class="clike">#include&lt;iostream&gt;
#include&lt;cstdio&gt;
#include&lt;string&gt;
//前序遍历和中序遍历可以唯一确定一棵二叉树，
//而对二叉排序树而言，相同元素的二叉排序树中
//序遍历一定相同，而不同元素二叉排序树使用前
//序遍历就可以发现不相同，所以只需要前序遍历
//两个二叉树，比较一下就可以判断
using namespace std;
string pre,in;
struct TreeNode{
    char data;
    TreeNode* leftchild;
    TreeNode* rightchild;
    TreeNode(char c):data(c),leftchild(NULL),rightchild(NULL){}
};
TreeNode* Insert(TreeNode* root,char x){
    if(root==NULL){
        root=new TreeNode(x);
    }
    else if(x&lt;root-&gt;data){
        root-&gt;leftchild=Insert(root-&gt;leftchild,x);
    }
    else if(x&gt;root-&gt;data){
        root-&gt;rightchild=Insert(root-&gt;rightchild,x);
    }
    return root;
}
string preorder(TreeNode* root){
    if(root==NULL) return &quot;#&quot;;
    return root-&gt;data+preorder(root-&gt;leftchild)+preorder(root-&gt;rightchild);
}
int main(){
    int n;
    while(cin&gt;&gt;n){
        if(n==0) break;
        string s; TreeNode* root=NULL;
        cin&gt;&gt;s;
        //构建初始的排序树
        for(int i=0;i&lt;s.size();i++){
            root=Insert(root,s[i]);
        }
        string pre=preorder(root);
        //构建用来比较的排序树
        for(int i=0;i&lt;n;i++){
            string str; TreeNode* T=NULL;
            cin&gt;&gt;str;
            for(int j=0;j&lt;str.size();j++){
                T=Insert(T,str[j]);
            }
            string pre1=preorder(T);
        //进行比较
            if(pre1==pre) cout&lt;&lt;&quot;YES&quot;&lt;&lt;endl;
            else cout&lt;&lt;&quot;NO&quot;&lt;&lt;endl;
        }
    }
    return 0;
}</code></pre>
<h2 id="二叉排序树最大路径"><a href="#二叉排序树最大路径" class="headerlink" title="二叉排序树最大路径"></a>二叉排序树最大路径</h2><p><strong>题目描述</strong><br>求二叉排序树中的最大路径</p>
<p><strong>输入</strong></p>
<blockquote>
<p>16<br>30 45 2 69 36 14 52 23 31 90 57 32 33 34 91 92</p>
</blockquote>
<p><strong>输出</strong></p>
<blockquote>
<p>11</p>
</blockquote>
<pre><code class="clike">#include&lt;bits/stdc++.h&gt;

using namespace std;

struct TreeNode{
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int data):data(data),left(NULL),right(NULL){}
};
int Max=0;
int a[100];
//测试数据
//30 45 2 69 36 14 52 23 31 90 57 32 33 34 91 92
TreeNode* CreatTree(TreeNode* root,int data){
    if(root==NULL){
        TreeNode* T=new TreeNode(data);
        return T;
    }
    if(data&lt;root-&gt;data) root-&gt;left=CreatTree(root-&gt;left,data);
    else if(data&gt;root-&gt;data) root-&gt;right=CreatTree(root-&gt;right,data);
    return root;
}

int MaxPath(TreeNode* root){
    if(root==NULL) return 0;
    int lh,rh,sum;
    //包括自己在内的长度
    lh=MaxPath(root-&gt;left)+1;
    rh=MaxPath(root-&gt;right)+1;
    //cout&lt;&lt;root-&gt;data&lt;&lt;&quot; &quot;&lt;&lt;lh&lt;&lt;&quot; &quot;&lt;&lt;rh&lt;&lt;endl;
    sum=lh+rh-1;
    Max=max(Max,sum);
    return lh&gt;rh?lh:rh;
}

void PreOrder(TreeNode* T){
    if(T==NULL) return ;
    cout&lt;&lt;T-&gt;data;
    PreOrder(T-&gt;left);
    PreOrder(T-&gt;right);
}

int main(){
    int n;
    cin&gt;&gt;n;
    TreeNode* root=NULL;
    for(int i=0;i&lt;n;i++){
        cin&gt;&gt;a[i];
        root=CreatTree(root,a[i]);
    }
    MaxPath(root);
    cout&lt;&lt;endl;
    cout&lt;&lt;Max;
}
</code></pre>
<h1 id="huffman树"><a href="#huffman树" class="headerlink" title="huffman树"></a>huffman树</h1><h2 id="huffman编码"><a href="#huffman编码" class="headerlink" title="huffman编码"></a>huffman编码</h2><p><strong>题目描述</strong><br>哈弗曼树问题：在”7.in”中<br>有几个数，和为1，进行哈弗曼编码，并把编码结果输出到”7.out”中。</p>
<p><strong>输入</strong></p>
<blockquote>
<p>0.1 0.15 0.2 0.25 0.3</p>
</blockquote>
<p><strong>输出</strong></p>
<blockquote>
<p>000<br>001<br>01<br>10<br>11</p>
</blockquote>
<p>PS:这道题我写了特别久，主要是优先队列存指针的问题，西八，太难了。</p>
<pre><code class="clike">#include&lt;bits/stdc++.h&gt;
using namespace std;

const int eps=1e-6;

struct HfNode{
    double weight;
    HfNode* left;
    HfNode* right;
    string code;
    HfNode(double weight):weight(weight),left(NULL),right(NULL),code(&quot;&quot;){}
    bool operator &gt;(const HfNode&amp; e)const{
        return weight&gt;e.weight;
    }
};

HfNode* Tree[10000];

void Huffman(HfNode* T){//遍历huffman树设编码
    //cout&lt;&lt;T.code&lt;&lt;endl;
    if(T-&gt;left!=NULL) {T-&gt;left-&gt;code=T-&gt;code+&quot;1&quot;;  Huffman(T-&gt;left);}
    if(T-&gt;right!=NULL) {T-&gt;right-&gt;code=T-&gt;code+&quot;0&quot;;  Huffman(T-&gt;right);}
    if(T-&gt;left==NULL&amp;&amp;T-&gt;right==NULL) cout&lt;&lt;T-&gt;weight&lt;&lt;&quot; &quot;&lt;&lt;T-&gt;code&lt;&lt;endl;//叶子结点
    return ;
}

//重要：std::priority_queue 存放的是自定义类型的指针时,解决方法是使用Compare
//类似于sort中定义的cmp
class Compare{
public:
    bool operator () (HfNode* &amp;a,HfNode* &amp;b) const{
        return a-&gt;weight&gt;b-&gt;weight;
    }
};

int main(){
    priority_queue &lt;HfNode*,vector&lt;HfNode*&gt;,Compare &gt; q;
    ifstream infile(&quot;in.txt&quot;);
    double n; string s;
    getline(infile,s);
    stringstream in(s);//这个在double会出现问题

    while(in&gt;&gt;n){
        HfNode* node=new HfNode(n);//在前面加new返回指针，不加new就是node的类型
        q.push(node);
    }

    int point;
    while(q.size()&gt;1){//建huffman树
        //分配空间
        HfNode* a=(HfNode*)malloc(sizeof(HfNode));
        HfNode* b=(HfNode*)malloc(sizeof(HfNode));
        HfNode* c=(HfNode*)malloc(sizeof(HfNode));
        a=q.top(); q.pop();
        b=q.top(); q.pop();
        double x=a-&gt;weight+b-&gt;weight;
        c=new HfNode(x);
        c-&gt;left=a; c-&gt;right=b;
        //cout&lt;&lt;c-&gt;left-&gt;weight&lt;&lt;&quot; &quot;&lt;&lt;c-&gt;right-&gt;weight&lt;&lt;endl;
        q.push(c);
    }
    Huffman(q.top());
}
</code></pre>
<h1 id="其余题型"><a href="#其余题型" class="headerlink" title="其余题型"></a>其余题型</h1><h2 id="层次遍历"><a href="#层次遍历" class="headerlink" title="层次遍历"></a>层次遍历</h2><p><strong>题目描述</strong><br>输出树的层次遍历的奇数层的所有结点。<br><strong>输入</strong></p>
<blockquote>
<p>A B C<br>B E<br>C F G</p>
</blockquote>
<p><strong>输出</strong></p>
<blockquote>
<p>第 1 层结点：A<br>第 3 层结点：E,F,G</p>
</blockquote>
<pre><code class="clike">#include&lt;iostream&gt;
#include&lt;fstream&gt;
#include&lt;vector&gt;
#include&lt;sstream&gt;
#include&lt;queue&gt;
using namespace std;

struct TreeNode{
    char data;
    TreeNode* left;
    TreeNode* right;
    int deep;
    TreeNode(char data,int deep):data(data),deep(deep),left(NULL),right(NULL){}
};
const int MAXN=100;
TreeNode* Tree[MAXN];//建树时一定要用这个，方便用内容去找到结点;

vector&lt;char&gt; v;

void Level_Order(TreeNode* T){
    queue&lt;TreeNode*&gt; q;
    q.push(T);
    while(!q.empty()){
        TreeNode* p=q.front();
        q.pop();
        if(p-&gt;deep%2==1) cout&lt;&lt;&quot;第&quot;&lt;&lt;p-&gt;deep&lt;&lt;&quot;层:&quot;&lt;&lt;p-&gt;data&lt;&lt;&quot; &quot;&lt;&lt;endl;
        if(p-&gt;left){
            q.push(p-&gt;left);
        }
        if(p-&gt;right){
            q.push(p-&gt;right);
        }

    }
}

int main(){
    ifstream infile(&quot;in.txt&quot;);
    string s;
    int i=1;
    while(getline(infile,s)){
        v.clear();
        char c;
        stringstream in(s);
        while(in&gt;&gt;c){
            v.push_back(c);
        }
        if(!Tree[v[0]-&#39;A&#39;]) Tree[v[0]-&#39;A&#39;]=new TreeNode(v[0],1);
        int deep=Tree[v[0]-&#39;A&#39;]-&gt;deep;
        for(int i=0;i&lt;v.size();i++) cout&lt;&lt;v[i]-&#39;A&#39;&lt;&lt;&quot; &quot;&lt;&lt;endl;
        if(v.size()==3){//参照这样的方法建树
            if(!Tree[v[1]-&#39;A&#39;]){//可以这样判断数组该处有没有值
                Tree[v[1]-&#39;A&#39;]=new TreeNode(v[1],deep+1);
            }
            if(!Tree[v[2]-&#39;A&#39;]){
                Tree[v[2]-&#39;A&#39;]=new TreeNode(v[2],deep+1);
            }
            Tree[v[0]-&#39;A&#39;]-&gt;left=Tree[v[1]-&#39;A&#39;];
            Tree[v[0]-&#39;A&#39;]-&gt;right=Tree[v[2]-&#39;A&#39;];
        }
        else if(v.size()==2){
            if(!Tree[v[1]-&#39;A&#39;]){
                Tree[v[1]-&#39;A&#39;]=new TreeNode(v[1],deep+1);
            }
            Tree[v[0]-&#39;A&#39;]-&gt;left=Tree[v[1]-&#39;A&#39;];
        }
        i++;
    }
    Level_Order(Tree[0]);
    //cout&lt;&lt;Tree[0]-&gt;left-&gt;left-&gt;data&lt;&lt;endl;//用这种方法来测试树是否建立成功


}
</code></pre>
<h2 id="FBI树"><a href="#FBI树" class="headerlink" title="FBI树"></a>FBI树</h2><p><strong>题目描述</strong><br>我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。FBI树是一种二叉树，它的结点类型也包括FF结点，BB结点和I结点三种。由一个长度为 2 ^N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：</p>
<ol>
<li>T的根结点为R，其类型与串S的类型相同；</li>
<li>若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。</li>
</ol>
<p>现在给定一个长度为2^N 的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。</p>
<p><strong>输入格式</strong><br>第一行是一个整数N(0≤N≤10)，</p>
<p>第二行是一个长度为2^N的“01”串。</p>
<p><strong>输出格式</strong><br>一个字符串，即FBI树的后序遍历序列。</p>
<p><strong>输入</strong></p>
<blockquote>
<p>3<br>10001011</p>
</blockquote>
<p><strong>输出</strong></p>
<blockquote>
<p>IBFBBBFIBFIIIFF</p>
</blockquote>
<pre><code class="clike">#include&lt;iostream&gt;
#include&lt;math.h&gt;
#include&lt;cstdio&gt;
#include&lt;cstdlib&gt;
using namespace std;

int n;
string str;

struct TreeNode{
    char data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char data):data(data),left(NULL),right(NULL){}
};

TreeNode* Tree[100000];
int p=0;
TreeNode* CreatTree(int Start,int End){
    string s=str.substr(Start,End-Start+1);
    //cout&lt;&lt;s&lt;&lt;endl;
    TreeNode* T=(TreeNode*)malloc(sizeof(TreeNode*));//为了防止指针被覆盖
    if(s.find(&quot;0&quot;)!=string::npos&amp;&amp;s.find(&quot;1&quot;)!=string::npos){
        //cout&lt;&lt;&quot;P:&quot;&lt;&lt;p&lt;&lt;&quot; &quot;&lt;&lt;&quot;F&quot;&lt;&lt;endl;
        Tree[p]=new TreeNode(&#39;F&#39;);
        T=Tree[p];
    }
    else if(s.find(&quot;0&quot;)!=string::npos&amp;&amp;s.find(&quot;1&quot;)==string::npos){
        //cout&lt;&lt;&quot;P:&quot;&lt;&lt;p&lt;&lt;&quot;B&quot;&lt;&lt;endl;
        Tree[p]=new TreeNode(&#39;B&#39;);
        T=Tree[p];
    }
    else if(s.find(&quot;0&quot;)==string::npos&amp;&amp;s.find(&quot;1&quot;)!=string::npos){
        //cout&lt;&lt;&quot;P:&quot;&lt;&lt;p&lt;&lt;&quot;I&quot;&lt;&lt;endl;
        Tree[p]=new TreeNode(&#39;I&#39;);
        T=Tree[p];
    }
    p++;
    if(s.size()==1){
        return T;
    }
    else{
        T-&gt;left=CreatTree(Start,Start+(End-Start)/2);
        T-&gt;right=CreatTree(End-(End-Start)/2,End);
    }
    return T;
}

void PostOrder(TreeNode* root){
    if(root==NULL) return ;
    PostOrder(root-&gt;left);
    PostOrder(root-&gt;right);
    cout&lt;&lt;root-&gt;data;
}

int main(){
    cin&gt;&gt;n;
    for(int i=1;i&lt;=pow(2,n);i++){
        char c;
        cin&gt;&gt;c;
        str=str+c;
    }
    //cout&lt;&lt;str&lt;&lt;endl;
    TreeNode* root=CreatTree(0,str.size()-1);
    PostOrder(Tree[0]);
}
</code></pre>
<h2 id="新二叉树"><a href="#新二叉树" class="headerlink" title="新二叉树"></a>新二叉树</h2><p><strong>题目描述</strong><br>输入一串二叉树，输出其前序遍历。</p>
<p><strong>输入格式</strong><br>第一行为二叉树的节点数 n。(1≤n≤26)<br>后面 n 行，每一个字母为节点，后两个字母分别为其左右儿子。空节点用 * 表示</p>
<p><strong>输出格式</strong><br>二叉树的前序遍历。</p>
<p><strong>输入</strong></p>
<blockquote>
<p>6<br>abc<br>bdi<br>cj*<br>d**<br>i**<br>j**</p>
</blockquote>
<p><strong>输出</strong></p>
<blockquote>
<p>abdicj</p>
</blockquote>
<pre><code class="clike">#include&lt;iostream&gt;

using namespace std;
int n;
struct TreeNode{
    char data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char data):data(data),left(NULL),right(NULL){};
};

TreeNode* Tree[10000];

void PreOrder(TreeNode* root){
    if(root==NULL) return ;
    cout&lt;&lt;root-&gt;data;
    PreOrder(root-&gt;left);
    PreOrder(root-&gt;right);
}

int main(){
    cin&gt;&gt;n;
    string s;
    char T=0; int i=n;//因为Tree[0]不一定是根结点!!!!
    while(n--){
        cin&gt;&gt;s;
        if(i==n+1) T=s[0];//记录根结点
        //别忘了每一个结点都要判断是否已经存在
        if(!Tree[s[0]-&#39;a&#39;]) Tree[s[0]-&#39;a&#39;]=new TreeNode(s[0]);
        if(s[1]!=&#39;*&#39;){
            if(!Tree[s[1]-&#39;a&#39;]) Tree[s[1]-&#39;a&#39;]=new TreeNode(s[1]);
            Tree[s[0]-&#39;a&#39;]-&gt;left=Tree[s[1]-&#39;a&#39;];
        }
        if(s[2]!=&#39;*&#39;){
            if(!Tree[s[2]-&#39;a&#39;]) Tree[s[2]-&#39;a&#39;]=new TreeNode(s[2]);
            Tree[s[0]-&#39;a&#39;]-&gt;right=Tree[s[2]-&#39;a&#39;];
        }
    }
    PreOrder(Tree[T-&#39;a&#39;]);
}
</code></pre>

            <hr>
          </div>
          <br>
          <div>
            <p>
            
              <span>
                <i class="iconfont icon-inbox"></i>
                
                  <a class="hover-with-bg" href="/categories/%E7%AE%97%E6%B3%95">算法</a>
                  &nbsp;
                
              </span>&nbsp;&nbsp;
            
            
              <span>
                <i class="iconfont icon-tag"></i>
                
                  <a class="hover-with-bg" href="/tags/c++">c++</a>
                
                  <a class="hover-with-bg" href="/tags/%E6%A0%91">树</a>
                
              </span>
            
            </p>
            
              <p class="note note-warning">本博客所有文章除特别声明外，均采用 <a href="https://zh.wikipedia.org/wiki/Wikipedia:CC_BY-SA_3.0%E5%8D%8F%E8%AE%AE%E6%96%87%E6%9C%AC" target="_blank" rel="nofollow noopener noopener">CC BY-SA 3.0协议</a> 。转载请注明出处！</p>
            
          </div>
        </div>
      </div>
    </div>
    <div class="d-none d-lg-block col-lg-2 toc-container">
      
  <div id="toc">
    <p class="h4"><i class="far fa-list-alt"></i>&nbsp;TOC</p>
    <div id="tocbot"></div>
  </div>

    </div>
  </div>
</div>

<!-- custom -->


<!-- Comments -->
<div class="col-lg-7 mx-auto nopadding-md">
  <div class="container comments mx-auto" id="comments">
    
      <br><br>
      
      
  <!--PC和WAP自适应版-->
  <div id="SOHUCS" sid='http://yoursite.com/2020/03/11/%E6%A0%91%E5%9E%8B%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E6%80%BB%E7%BB%93/'></div>
  <script type="text/javascript">
    (function () {
      var appid = 'cyuGAy6Y7';
      var conf = '';
      var width = window.innerWidth || document.documentElement.clientWidth;
      if (width < 960) {
        var head = document.getElementsByTagName('head')[0] || document.head || document.documentElement;
        var script = document.createElement('script');
        script.type = 'text/javascript';
        script.charset = 'utf-8';
        script.id = 'changyan_mobile_js';
        script.src = 'https://changyan.sohu.com/upload/mobile/wap-js/changyan_mobile.js?client_id=' + appid + '&conf=' + conf;
        head.appendChild(script);
      } else {
        var loadJs = function (d, a) {
          var c = document.getElementsByTagName('head')[0] || document.head || document.documentElement;
          var b = document.createElement('script');
          b.setAttribute('type', 'text/javascript');
          b.setAttribute('charset', 'UTF-8');
          b.setAttribute('src', d);
          if (typeof a === 'function') {
            if (window.attachEvent) {
              b.onreadystatechange = function () {
                var e = b.readyState;
                if (e === 'loaded' || e === 'complete') {
                  b.onreadystatechange = null;
                  a();
                }
              };
            } else {
              b.onload = a;
            }
          }
          c.appendChild(b);
        };
        loadJs('https://changyan.sohu.com/upload/changyan.js', function () {
          window.changyan.api.config({ appid: appid, conf: conf });
        });
      }
    })(); </script>


    
  </div>
</div>

    
  </main>

  
    <a class="z-depth-1" id="scroll-top-button" href="#" role="button">
      <i class="fa fa-chevron-up scroll-top-arrow" aria-hidden="true"></i>
    </a>
  

  
    <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">Search</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">keyword</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
  

  <footer class="mt-5">
  <div class="text-center py-3">
    <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><b>Hexo</b></a>
    <i class="iconfont icon-love"></i>
    <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener"> <b>Fluid</b></a>
    <br>

    
  
    <!-- 不蒜子统计PV -->
    
    &nbsp;<span id="busuanzi_container_site_pv">总访问量 
          <span id="busuanzi_value_site_pv"></span> 次</span>&nbsp;
  
  
    <!-- 不蒜子统计UV -->
    
    &nbsp;<span id="busuanzi_container_site_uv">总访客数 
            <span id="busuanzi_value_site_uv"></span> 人</span>&nbsp;
  
  <br>



    


    <!-- cnzz Analytics icon -->
    

  </div>
</footer>

<!-- SCRIPTS -->
<script src="https://cdn.staticfile.org/jquery/3.4.1/jquery.min.js" ></script>
<script src="https://cdn.staticfile.org/popper.js/1.15.0/umd/popper.min.js" ></script>
<script src="https://cdn.staticfile.org/twitter-bootstrap/4.3.1/js/bootstrap.min.js" ></script>
<script src="https://cdn.staticfile.org/mdbootstrap/4.8.9/js/mdb.min.js" ></script>
<script src="/js/main.js" ></script>


  <script src="/js/lazyload.js" ></script>



  
    <script src="https://cdn.staticfile.org/tocbot/4.8.0/tocbot.min.js" ></script>
  
  <script src="/js/post.js" ></script>



  <script src="https://cdn.staticfile.org/smoothscroll/1.4.10/smooth-scroll.min.js" ></script>



  <script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" ></script>


<!-- Plugins -->


  
    <!-- Baidu Analytics -->
    <script>
      var _hmt = _hmt || [];
      (function () {
        var hm = document.createElement("script");
        hm.src = "https://hm.baidu.com/hm.js?6a61255581242c8c58471dfbffd3bd66# 百度统计的Key，参见 https://tongji.baidu.com/sc-web/10000033910/home/site/getjs?siteId=13751376 代码获取中 hm.js? 后边的字符串";
        var s = document.getElementsByTagName("script")[0];
        s.parentNode.insertBefore(hm, s);
      })();
    </script>
  

  

  

  

  <!-- cnzz Analytics -->
  



  <script src="https://cdn.staticfile.org/prettify/r298/prettify.min.js" ></script>
  <script>
    $(document).ready(function () {
      $('pre').addClass('prettyprint  linenums');
      prettyPrint();
    })
  </script>



  <script src="https://cdn.staticfile.org/typed.js/2.0.10/typed.min.js" ></script>
  <script>
    var typed = new Typed('#subtitle', {
      strings: [
        '  ',
        "树形数据结构总结&nbsp;",
      ],
      cursorChar: "_",
      typeSpeed: 70,
      loop: false,
    });
    typed.stop();
    $(document).ready(function () {
      $(".typed-cursor").addClass("h2");
      typed.start();
    });
  </script>



  <script src="https://cdn.staticfile.org/anchor-js/4.2.0/anchor.min.js" ></script>
  <script>
    anchors.options = {
      placement: "right",
      visible: "false",
      
    };
    var el = "h1,h2,h3,h4,h5,h6".split(",");
    var res = [];
    for (item of el) {
      res.push(".markdown-body > " + item)
    }
    anchors.add(res.join(", "))
  </script>



  <script src="/js/local-search.js" ></script>
  <script>
    var path = "/local-search.xml";
    var inputArea = document.querySelector("#local-search-input");
    inputArea.onclick = function () {
      getSearchFile(path);
      this.onclick = null
    }
  </script>



  <script src="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.js" ></script>
  <script>
    $("#post img:not(.no-zoom img, img[no-zoom])").each(
      function () {
        var element = document.createElement("a");
        $(element).attr("data-fancybox", "images");
        $(element).attr("href", $(this).attr("src"));
        $(this).wrap(element);
      }
    );
  </script>





  
  
    <script type="text/javascript">
      //定义获取词语下标
      var a_idx = 0;
      jQuery(document).ready(function ($) {
        //点击body时触发事件
        $("body").click(function (e) {
          //需要显示的词语
          var a = new Array("富强", "民主", "文明", "和谐", "自由", "平等", "公正", "法治", "爱国", "敬业", "诚信", "友善");
          //设置词语给span标签
          var $i = $("<span/>").text(a[a_idx]);
          //下标等于原来下标+1  余 词语总数
          a_idx = (a_idx + 1) % a.length;
          //获取鼠标指针的位置，分别相对于文档的左和右边缘。
          //获取x和y的指针坐标
          var x = e.pageX, y = e.pageY;
          //在鼠标的指针的位置给$i定义的span标签添加css样式
          $i.css({
            "z-index": 999,
            "top": y - 20,
            "left": x,
            "position": "absolute",
            "font-weight": "bold",
            "color": rand_color()
          });
          // 随机颜色
          function rand_color() {
            return "rgb(" + ~~(255 * Math.random()) + "," + ~~(255 * Math.random()) + "," + ~~(255 * Math.random()) + ")"
          }
          //在body添加这个标签
          $("body").append($i);
          //animate() 方法执行 CSS 属性集的自定义动画。
          //该方法通过CSS样式将元素从一个状态改变为另一个状态。CSS属性值是逐渐改变的，这样就可以创建动画效果。
          //详情请看http://www.w3school.com.cn/jquery/effect_animate.asp
          $i.animate({
            //将原来的位置向上移动180
            "top": y - 180,
            "opacity": 0
            //1500动画的速度
          }, 1500, function () {
            //时间到了自动删除
            $i.remove();
          });
        });
      })
      ;
    </script>
  



  <script>(function (i, s, o, g, r, a, m) {
      i['DaoVoiceObject'] = r;
      i[r] = i[r] ||
        function () {
          (i[r].q = i[r].q || []).push(arguments);
        };
      i[r].l = 1 * new Date();
      a = s.createElement(o);
      m = s.getElementsByTagName(o)[0];
      a.async = 1;
      a.src = g;
      a.charset = 'utf-8';
      m.parentNode.insertBefore(a, m);
    })(window, document, 'script', ('https:' === document.location.protocol ? 'https:' : 'http:') + "//widget.daovoice.io/widget/246e9537.js", 'daovoice');
    daovoice('init', {
      app_id: "246e9537",
    });
    daovoice('update');
  </script>




<script src="/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"pluginModelPath":"assets/","model":{"jsonPath":"/live2dw/assets/wanko.model.json"},"display":{"position":"right","width":150,"height":300},"mobile":{"show":false},"log":false,"pluginJsPath":"lib/","pluginRootPath":"live2dw/","tagMode":false});</script></body>
</html>
